Lower bounds on the minimum average distance of binary codes

Let β(n,M) denote the minimum average Hamming distance of a binary code of length n and cardinality M. In this paper we consider lower bounds on β(n,M). All the known lower bounds on β(n,M) are useful when M is at least of size about 2ⁿ⁻¹/n. We derive new lower bounds which give good estimations when size of M is about n. These bounds are obtained using a linear programming approach. In particular, it is proved that lim_n→∞β(n,2n)=5/2. We also give a new recursive inequality for β(n,M).     

Undetected error probability of q-ary constant weight codes

In this paper, we introduce a new combinatorial invariant called q-binomial moment for q-ary constant weight codes. We derive a lower bound on the q-binomial moments and introduce a new combinatorial structure called generalized (s, t)-designs which could achieve the lower bounds. Moreover, we employ the q-binomial moments to study the undetected error probability of q-ary constant weight codes. A lower bound on the undetected error probability for q-ary constant weight codes is obtained. This lower bound extends and unifies the related results of Abdel-Ghaffar for q-ary codes and Xia-Fu-Ling for binary constant weight codes. Finally, some q-ary constant weight codes which achieve the lower bounds are found.      

Construction of optimal ternary constant weight codes via Bhaskar Rao designs

In this note, we consider a construction for optimal ternary constant weight codes (CWCs) via Bhaskar Rao designs (BRDs). The known existence results for BRDs are employed to generate many new optimal nonlinear ternary CWCs with constant weight 4 and minimum Hamming distance 5.     

Nonbinary quantum error-correcting codes from algebraic curves

We give a new exposition and proof of a generalized CSS construction for nonbinary quantum error-correcting codes. Using this we construct nonbinary quantum stabilizer codes with various lengths, dimensions, and minimum distances from algebraic curves. We also give asymptotically good nonbinary quantum codes from a Garcia–Stichtenoth tower of function fields which are constructible in polynomial time.     

On diameter perfect constant-weight ternary codes

From cosets of binary Hamming codes we construct diameter perfect constant-weight ternary codes with weight n-1 (where n is the code length) and distances 3 and 5. The class of distance 5 codes has parameters unknown before.     

A construction of fully diverse unitary space-time codes

Fully diverse unitary space-time codes are useful in multiantenna communications, especially in multiantenna differential modulation. Recently, two constructions of parametric fully diverse unitary space-time codes for three antennas system have been introduced. We propose a new construction method based on the constructions. In the present paper, fully diverse codes for systems of odd prime number antennas are obtained from this construction. Space-time codes from present construction are found to have bet...     

Skew codes of prescribed distance or rank

In this paper we generalize the notion of cyclic code and construct codes as ideals in finite quotients of non-commutative polynomial rings, so called skew polynomial rings of automorphism type. We propose a method to construct block codes of prescribed rank and a method to construct block codes of prescribed distance. Since there is no unique factorization in skew polynomial rings, there are much more ideals and therefore much more codes than in the commutative case. In particular we obtain a [40, 23, 10]₄ code by imposing a distance and a [42,14,21]₈ code by imposing a rank, which both improve by one the minimum distance of the previously best known linear codes of equal length and dimension over those fields. There is a strong connection with linear difference operators and with linearized polynomials (or q-polynomials) reviewed in the first section.      

On proper secrets, (<Emphasis Type="Italic">t</Emphasis>, <Emphasis Type="Italic">k</Emphasis>)-bases and linear codes

This paper contains three parts where each part triggered and motivated the subsequent one. In the first part (Proper Secrets) we study the Shamir’s “k-out-of-n” threshold secret sharing scheme. In that scheme, the dealer generates a random polynomial of degree k−1 whose free coefficient is the secret and the private shares are point values of that polynomial. We show that the secret may, equivalently, be chosen as any other point value of the polynomial (including the point at infinity), but, on the other hand, setting the secret to be any other linear combination of the polynomial coefficients may result in an imperfect scheme. In the second part ((t, k)-bases) we define, for every pair of integers t and k such that 1 ≤ t ≤ k−1, the concepts of (t, k)-spanning sets, (t, k)-independent sets and (t, k)-bases as generalizations of the usual concepts of spanning sets, independent sets and bases in a finite-dimensional vector space. We study the relations between those notions and derive upper and lower bounds for the size of such sets. In the third part (Linear Codes) we show the relations between those notions and linear codes. Our main notion of a (t, k)-base bridges between two well-known structures: (1, k)-bases are just projective geometries, while (k−1, k)-bases correspond to maximal MDS-codes. We show how the properties of (t, k)-independence and (t, k)-spanning relate to the notions of minimum distance and covering radius of linear codes and how our results regarding the size of such sets relate to known bounds in coding theory. We conclude by comparing between the notions that we introduce here and some well known objects from projective geometry.      

On the upper bounds of the minimum number of rows of disjunct matrices

A 0-1 matrix is d-disjunct if no column is covered by the union of any d other columns. A 0-1 matrix is (d; z)-disjunct if for any column C and any d other columns, there exist at least z rows such that each of them has value 1 at column C and value 0 at all the other d columns. Let t(d, n) and t(d, n; z) denote the minimum number of rows required by a d-disjunct matrix and a (d; z)-disjunct matrix with n columns, respectively. We give a very short proof for the currently best upper bound on t(d, n). We also generalize our method to obtain a new upper bound on t(d, n; z). The work of Y. Cheng and G. Lin is supported by Natural Science and Engineering Research Council (NSERC) of Canada, and the Alberta Ingenuity Center for Machine Learning (AICML) at the University of Alberta. The work of D.-Z. Du is partially supported by National Science Foundation under grant No.CCF0621829.